// https://www.lintcode.com/problem/maximal-rectangle/description

class Solution {
public:
    /**
     * @param matrix: a boolean 2D matrix
     * @return: an integer
     */
    //法一：单调栈
    int maximalRectangle(vector<vector<bool>> &matrix) {
        if (matrix.empty())
            return 0;
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<int>> rec(n, vector<int>(m + 1));
        int res = 0;
        for (int i = 0; i < n; ++i) {
            stack<int> stack;
            for (int j = 0; j <= m; ++j) {
                if (j == m || matrix[i][j] == 0) {
                    rec[i][j] = 0;
                } else {
                    rec[i][j] = 1;
                    if (i > 0) {
                        rec[i][j] += rec[i - 1][j];
                    }  
                }
                while (!stack.empty() && rec[i][j] <= rec[i][stack.top()]) {
                    int h = rec[i][stack.top()];
                    stack.pop();
                    // int l = stack.top() + 1;
                    int l = stack.empty() ? 0 : (stack.top() + 1);
                    int r = j - 1;
                    res = max(res, (r - l + 1) * h);
                }
                stack.push(j);
            }
        }
        return res;
    }
    
    //法二：DP
    // int maximalRectangle(vector<vector<bool>> &matrix) {
    //     if (matrix.empty())
    //         return 0;
    //     int n = matrix.size();
    //     int m = matrix[0].size();
    //     vector<vector<int>> up(n, vector<int>(m));
    //     vector<vector<int>> left(n, vector<int>(m));
    //     vector<vector<int>> right(n, vector<int>(m));
    //     int res = 0;
    //     for (int i = 0; i < n; ++i) {
    //         for (int j = 0; j < m; ++j) {
    //             if (!matrix[i][j]) {
    //                 up[i][j] = 0;
    //             } else {
    //                 up[i][j] = 1;
    //                 if (i > 0) {
    //                     up[i][j] += up[i - 1][j];
    //                 }
    //             }
    //         }
    //         int l = 0;
    //         for (int j = 0; j < m; ++j) {
    //             if (!matrix[i][j]) {
    //                 l = 0;
    //                 left[i][j] = 0;
    //             } else {
    //                 ++l; //要重新记，不好用前面的做dp
    //                 left[i][j] = l;
    //                 if (i > 0 && matrix[i - 1][j] && left[i - 1][j] < left[i][j]) { 
    //                     //重要，如果上面的边短，就更新成上面的
    //                     left[i][j] = left[i - 1][j];
    //                 }
    //             }
    //         }
    //         int r = 0;
    //         for (int j = m - 1; j >= 0; --j) {
    //             if (!matrix[i][j]) {
    //                 r = 0;
    //                 right[i][j] = 0;
    //             } else {
    //                 ++r;
    //                 right[i][j] = r;
    //                 if (i > 0 && matrix[i - 1][j] && right[i - 1][j] < right[i][j]) {
    //                     right[i][j] = right[i - 1][j];
    //                 }
    //             }
    //         }
    //     }
    //     for (int i = 0; i < n; ++i) {
    //         for (int j = 0; j < m; ++j) {
    //             res = max(res, up[i][j] * (left[i][j] + right[i][j] - 1));
    //         }
    //     }
    //     return res;
    // }
};